/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/k-sum-ii
   @Language: C++
   @Datetime: 16-02-09 08:52
   */

class Solution {
	void kSumIICore(vector<int> &A,int k,int tar,int pos
			,vector<int> &vs, vector<vector<int> > &ans){
		if (tar==0 && k==vs.size()){
			ans.push_back(vs);
			return;
		}
		if (tar<=0 || pos>=A.size()) return;
		// select current pos num, or not
		vs.push_back(A[pos]);
		kSumIICore(A,k,tar-A[pos],pos+1,vs,ans);
		vs.pop_back();
		kSumIICore(A,k,tar,pos+1,vs,ans);
	}

public:
	/**
	 * @param A: an integer array.
	 * @param k: a positive integer (k <= length(A))
	 * @param target: a integer
	 * @return a list of lists of integer 
	 * Tip: Using DFS
	 */
	vector<vector<int> > kSumII(vector<int> &A, int k, int tar) {
		// write your code here
		vector<int> vs;
		vector<vector<int> > ans;
		kSumIICore(A,k,tar,0,vs,ans);
		return ans;
	}
};
